﻿#include "sort.h"
#include "stack.h"

// 打印数组
void PrintArray(int* arr, int length)
{
	for (int i = 0; i < length; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

//冒泡排序（从小到大）
//void BubbleSort(int* arr, int length)
//{
//	if (length <= 1) //不超过1个元素的数组，没必要排序
//		return;
//
//	//外层循环只控制排序的趟数
//	for (int i = 0; i < length - 1; ++i)
//	{
//		//内层循环控制元素的大小比较和交换位置
//		for (int j = 0; j < length - i - 1; ++j) //每趟比较的次数都会减少
//		{
//			if (arr[j] > arr[j + 1])  //前面的数据如果比后面的数据大
//			{
//				//交换元素位置
//				Swap(&arr[j], &arr[j + 1]);
//			}
//		} //end for j
//
//	} //end for i
//}


// 冒泡排序优化（从大到小）
void BubbleSort(int* arr, int length)
{
	if (length <= 1) //不超过1个元素的数组，没必要排序
		return;

	//外层循环只控制排序的趟数
	for (int i = 0; i < length - 1; ++i)
	{
		bool cgflag = false;//表本趟冒泡排序是否发生过记录交换，false：无；true：有
		//内层循环控制元素的大小比较和交换位置
		for (int j = 0; j < length - i - 1; ++j) //每趟比较的次数都会减少
		{
			if (arr[j] > arr[j + 1])  //前面的数据如果比后面的数据大
			{
				//交换元素位置
				Swap(&arr[j], &arr[j + 1]);
				cgflag = true; //标记本趟冒泡排序发生过记录交换(可能1次或者多次)
			}
		}
		if (cgflag == false) //本趟冒泡排序没有发生过记录交换，表示整个冒泡排序结束
			break;
	}
}

//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——

// 直接插入排序
// 时间复杂度(最坏)：O(length^2) -- 逆序
// 时间复杂度(最好)：O(length) -- 顺序有序

//直接插入排序（从小到大）
void InsertSort(int* arr, int length) //arr：要排序的数组元素，length：数组中元素数量
{
	if (length <= 1) //不超过1个元素的数组，没必要排序
		return;

	for (int i = 1; i < length; ++i) //从第2个元素（下标为1）开始比较
	{
		if (arr[i] < arr[i - 1])
		{
			int temp = arr[i];   //暂存arr[i]值，防止后续移动元素时值被覆盖
			int j;
			for (j = i - 1; j >= 0 && arr[j] > temp; --j) //检查所有前面排好序的元素
			{
				arr[j + 1] = arr[j]; //所有大于temp的元素都向后移动
			}
			arr[j + 1] = temp; //复制数据到插入位置，注意j因为被减了1，这里加回来
		}
	}
	return;
}


//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——


//希尔排序（从小到大）
void ShellSort(int* arr, int length)
{
	if (length <= 1) //不超过1个元素的数组，没必要排序
		return;

	int Dim = length / 2; // Dim：增量，取值分别为7、3、1
	while (Dim >= 1)
	{
		// 从 arr[Dim] 开始，向后遍历数组。
		// 对于每个元素 arr[i]，我们将其与 Dim 间隔之前的元素进行比较和插入排序。
		for (int i = Dim; i < length; ++i) //i值每次改变可以处理到不同的子序列
		{
			if (arr[i] < arr[i - Dim])
			{
				int temp = arr[i];//暂存arr[i]值，防止后续移动元素时值被覆盖
				int j;
				for (j = i - Dim; j >= 0 && arr[j] > temp; j -= Dim) //检查所有前面排好序的元素
				{
					//所有大于temp的元素都向后移动
					arr[j + Dim] = arr[j]; //大于temp的元素都向后移动
				}
				arr[j + Dim] = temp; //复制数据到插入位置，注意j因为被减了Dim，这里加回来
			}
		}

		Dim /= 2; //Dim减半，继续下一趟排序
	}
	return;
}

//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——


//简单选择排序（从小到大）
//void SelectSort(int* arr, int length)
//{
//	for (int i = 0; i < length - 1; ++i) //一共要进行length-1趟
//	{
//		int minidx = i; //保存最小元素位置
//
//		//在arr[i]到arr[length-1]中选择最小值
//		for (int j = i + 1; j < length; ++j)
//		{
//			if (arr[j] < arr[minidx])
//				minidx = j; //保存最小元素值位置
//		}
//
//		if (minidx != i)
//		{
//			Swap(&arr[i], &arr[minidx])
//		}
//	}
//}

//简单选择排序优化（从小到大）
//与传统的选择排序不同，这段代码每次找到数组当前范围内的最小值和最大值，并分别将它们放置在当前范围的最前端和最后端，
//从而每次可以将范围缩小两格而不是一格。
void SelectSort(int* arr, int length)
{
	int begin = 0, end = length - 1; // 当前正在处理的数组的左右边界。

	while (begin < end)
	{
		int maxidx = begin, minidx = begin; 
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] > arr[maxidx]) 
			{
				maxidx = i; 
			}
			if (arr[i] < arr[minidx]) 
			{
				minidx = i;
			}
		} // 内部循环：找到当前范围内的最小值和最大值的索引

		Swap(&arr[begin], &arr[minidx]); // 将当前范围内的最小值交换到begin的位置。
		if (begin == maxidx) 
		{
			maxidx = minidx; // 如果最大值最初在begin位置，那么经过前面的最小值交换后，maxidx应该更新为minidx
		}
		Swap(&arr[end], &arr[maxidx]); // 将当前范围内的最大值交换到end的位置。
		
		// 增加begin，减少end，缩小处理范围。
		++begin;
		--end;
	}
}

//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
// 堆排序

// 堆的向下调整(下沉)
void AdjustDown(int* arr, int length, int parent)
{
	int child = 2 * parent + 1; //先设左孩子节点较大

	while (child < length) //向下调整的终止条件为：双亲节点已经下沉到叶子节点位置，其child已大于数组的size越界
	{
		//选出左右孩子节点中较大的
		if (child + 1 < length && arr[child + 1] > arr[child]) //若右孩子节点存在且大于左孩子节点
		{
			child++; //设右孩子节点较大
		}
		//到这child为左右孩子中较大的节点

		if (arr[child] > arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child; //交换数据之后，可能就会影响到下一层了。所以还要继续向下调整
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* arr, int length)
{
	// 升序 -- 建大堆
	// 降序 -- 建小堆

	// 1.从第一个非叶子节点(分支节点)开始，往前进行向下调整建堆
	for (int i = (length / 2) - 1; i >= 0; i--) //时间复杂度：O(length)，推荐
	{
		AdjustDown(arr, length, i);
	}

	//2.对堆节点进行调整排序
	//方法：第0个节点与最后一个节点交换、再从第0个节点开始往后进行向下调整
	int end = length - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}


//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
// 快速排序

// 声明三位取中函数
int GetMidIndex(int* arr, int left, int right);


/*
1.Hoare分区方法（HoarePartition）：

1. 选择一个基准元素（通常是数组的第一个元素），将其值保存在key中。使用两个指针left和right分别指向数组的左右边界。
2. 从右边开始，将right指针向左移动，直到找到第一个小于基准元素的值；
从左边开始，将left指针向右移动，直到找到第一个大于基准元素的值；
然后交换 left 和 right 指指向的值。
3. 将left指针继续右移，right指针继续左移。直到left 指针大于等于right指针。
4. 将基准元素的值放入left指针所指的位置，此时left指针（以及right指针）指向的位置就是分区的分界点。 
*/
int HoarePartition(int* arr, int left, int right)
{
	int mididx = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mididx]);

	int keyi = left;
	while (left < right)
	{
		// 右指针从右往左找比key小的值
		while (left < right && arr[right] >= arr[keyi])
		{
			--right;
		}
		// 左指针从左往右找比key大的值
		while (left < right && arr[left] <= arr[keyi])
		{
			++left;
		}

		Swap(&arr[left], &arr[right]);
	}

	Swap(&arr[keyi], &arr[left]);

	return left;
}

/*
2.Lomuto分区方法（LomutoPartition）：

1.选择一个基准元素（通常是数组的第一个元素），将其值保存在key中。使用两个指针left和right分别指向数组的左右边界。
2.从右边开始，找到第一个小于基准元素的值，将右指针right向左移动。
  将找到的小于基准元素的值赋给基准元素所在的空位（hole），并将hole更新为右指针right。
3.从左边开始，找到第一个大于基准元素的值，将左指针left向右移动。
  将找到的大于基准元素的值赋给基准元素所在的空位（hole），并将hole更新为左指针left。
4.继续执行上述步骤，直到左指针left大于等于右指针right。
  最后将基准元素的值放入最后一个空位hole中。返回hole作为分区的分界点。
*/
int LomutoPartition(int* arr, int left, int right)
{
	int mididx = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mididx]);

	int key = arr[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && arr[right] > key)
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;

		while (left < right && arr[left] <= key)
		{
			++left;
		}
		arr[hole] = arr[left];
		hole = left;
	}

	arr[hole] = key;

	return hole;
}

// Lomuto分区方法优化（LomutoPartition）：
int LomutoPartition2(int* arr, int left, int right)
{
	int mididx = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mididx]);

	int key = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] > key)
		{
			--right;
		}
		arr[left] = arr[right];

		while (left < right && arr[left] <= key)
		{
			++left;
		}
		arr[right] = arr[left];
	}

	arr[left] = key;

	return left;
}

/*
3.前后指针法（DoublePointer）：

1. 选择一个基准元素（通常是数组的第一个元素），将其值保存在key中。初始时prev 指针指向序列开头， cur 指针指向prev 指针的后一个位置。
2. 若cur 指向的数据大于 key，则cur ++；若cur 指向的数据小于 key，则prev 先后移一位++，然后与 cur 指针指向的数据交换，最后cur 再++.
3. 重复上述过程，直到 cur指针为空，最后将prev 指向的内容与一开始保存的key 值进行交换。
4. 结束，此时key 左边的数据都比 key 小，key 右边的数据都比key 大，分区完毕。

上述过程类似于：
1.最开始prev与cur相邻
2.当cur遇到比key大的值后，它们之间的值都是比key大的值
3.相当于把prev与cur之间比key大的值翻滚式的往右边推，同时把小的换到左边
*/

int DoublePointerPartition(int* arr, int left, int right)
{
	int mididx = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mididx]);

	int prev = left;
	int cur = left + 1;
	int key = arr[left];

	while (cur <= right)
	{
		if (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}

		++cur;
	}

	Swap(&arr[prev], &key);

	return prev;
}

void QuickSort(int* arr, int begin, int end)
{
	// 在快速排序算法中，当需要排序的子数组的长度为0或1时，已经是有序的，不需要再进行排序。
	// 因此，当begin大于等于end时，即子数组的长度为0或1，就可以终止递归，直接返回。
	if (begin >= end)
		return;
	int keyi = LomutoPartition2(arr, begin, end);
	// [begin, keyi-1] keyi [keyi+1, end]

	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}


// 快速排序分区枢轴优化 (三数取中) 
// 选取arr[left],arr[mid],arr[right]中的中位数。
// 注意！mid只是索引的中位数，不代表arr[mid]三个数中的中位数，所以需要判断大小
int GetMidIndex(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2;

	// 数组的头部是中位数
	if ((arr[mid] < arr[left] && arr[left] < arr[right])
		|| (arr[right] < arr[left] && arr[left] < arr[mid]))
	{
		return left;
	}
	// 数组的中部是中位数
	else if ((arr[left] < arr[mid] && arr[mid] < arr[right])
		|| (arr[right] < arr[mid] && arr[mid] < arr[left]))
	{
		return mid;
	}
	// 数组的尾部是中位数
	else
	{
		return right;
	}
}

// 快速排序的非递归方式
/*
1.创建一个栈，用于保存待处理的子数组的起始和结束位置。
2.将整个数组的起始和结束位置压入栈。
3.进入循环，直到栈为空。
4.在每次循环中，从栈中弹出一个子数组的起始和结束位置。
5.使用划分函数将该子数组分为两部分，并得到分割元素的索引。
  如果分割元素右边的子数组长度大于1，则将右半部分的起始和结束位置压入栈。
  如果分割元素左边的子数组长度大于1，则将左半部分的起始和结束位置压入栈。
  循环继续，直到栈为空。
6.所有子数组都被处理完毕，排序完成。

使用栈来实现快速排序的非递归版本的主要思想是模拟递归过程。通过将待处理的子数组的起始和结束位置保存在栈中，可以避免使用递归时的系统栈溢出问题。
每次从栈中弹出一个子数组并进行划分，然后根据划分的结果将子数组的起始和结束位置压入栈。该过程会持续进行，直到所有的子数组都被处理完毕，排序完成。
*/
void QuickSortNonR(int* arr, int begin, int end)
{
	Stack st;  // 创建一个栈用于保存待处理的子数组的起始和结束位置
	StackInit(&st);  // 初始化栈
	StackPush(&st, end);  // 将结束位置压入栈
	StackPush(&st, begin);  // 将起始位置压入栈

	while (!StackEmpty(&st))  // 当栈不为空时进行循环
	{
		int left = StackTop(&st);  // 弹出栈顶元素作为子数组的起始位置
		StackPop(&st);

		int right = StackTop(&st);  // 弹出栈顶元素作为子数组的结束位置
		StackPop(&st);

		int keyi = HoarePartition(arr, left, right);  // 使用划分函数将子数组划分为两部分，并返回分割元素的索引

		if (keyi + 1 < right)  // 如果分割元素右边的子数组长度大于1，则将右半部分的起始和结束位置压入栈
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (left < keyi - 1)  // 如果分割元素左边的子数组长度大于1，则将左半部分的起始和结束位置压入栈
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}
	StackDestroy(&st);  // 销毁栈

}


// 快速排序方法之三路归并
/*
快速排序的三路归并版本是一种对具有大量重复元素的数组进行排序的改进版本。它通过将数组分为小于、等于和大于分割元素的三部分来实现排序。下面是该算法的实现逻辑：
1. 选择一个分割元素，可以是数组中的任意一个元素。通常为了避免最坏情况的发生，我们会选择随机的分割元素。
2. 定义三个指针，分别表示小于分割元素的部分、等于分割元素的部分和大于分割元素的部分的起始位置。初始时，这三个指针都指向数组的起始位置。
3. 从数组的第二个元素开始遍历，直到遍历到数组的最后一个元素。
4. 对于每个遍历到的元素，将其与分割元素进行比较：
- 如果该元素小于分割元素，将其与小于部分的指针指向的元素交换位置，并将小于部分的指针和等于部分的指针都向右移动。
- 如果该元素大于分割元素，将其与大于部分的指针指向的元素交换位置，并将大于部分的指针向左移动。
- 如果该元素等于分割元素，将等于部分的指针向右移动。
5. 遍历结束后，整个数组被分为小于分割元素、等于分割元素和大于分割元素的三个部分。
6. 递归地对小于和大于部分进行排序，即对小于部分进行快速排序和对大于部分进行快速排序。
7. 递归结束后，数组就被排序好了。
通过使用三路归并进行快速排序，可以有效地提高对具有大量重复元素的数组进行排序的效率。它减少了重复比较的次数，将具有相同值的元素放在一起，提高了算法的性能。
*/
void QuickSort3Ways(int* arr, int begin, int end)
{
	if (begin >= end)  // 如果起始位置大于等于结束位置，则表示只有一个元素或者没有元素，已经有序，直接返回
	{
		return;
	}

	int left = begin;  // 左指针初始位置为起始位置
	int right = end;  // 右指针初始位置为结束位置
	int cur = left + 1;  // 当前指针初始位置为左指针的下一个位置

	int mididx = GetMidIndex(arr, left, right);  // 获取中间元素的索引
	Swap(&arr[left], &arr[mididx]);  // 将中间元素与起始元素交换位置，以确保选择的分割元素是随机的
	int key = arr[left];  // 分割元素为起始元素

	while (cur <= right)  // 当当前指针小于等于右指针时进行循环
	{
		if (arr[cur] < key)  // 如果当前元素小于分割元素
		{
			Swap(&arr[left], &arr[cur]);  // 将当前元素与左指针指向的元素交换位置
			++left;  // 左指针向右移动
			++cur;  // 当前指针向右移动
		}
		else if (arr[cur] > key)  // 如果当前元素大于分割元素
		{
			Swap(&arr[right], &arr[cur]);  // 将当前元素与右指针指向的元素交换位置
			--right;  // 右指针向左移动
		}
		else  // 如果当前元素等于分割元素
		{
			++cur;  // 当前指针向右移动
		}
	}

	// 将数组分为小于分割元素、等于分割元素和大于分割元素的三部分
	// 小 l r 大
	// [begin, left-1] [left, right] [right+1, end]
	QuickSort3Ways(arr, begin, left - 1);  // 对小于分割元素的部分进行递归排序
	QuickSort3Ways(arr, right + 1, end);  // 对大于分割元素的部分进行递归排序
}

//1.arr[c] < key :交换c和l位置的值，++l，++c 
//1.arr[c] > key :交换c和r位置的值，--r 
//1.arr[c] == key :++c
// 三路划分的本质：
//1.小的甩到左边，大的甩到右边
//2.跟key相等的值推到中间




//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
// 归并排序
// 时间复杂度：O(logN * length)
// 空间复杂度：O(length)
//void _MergeSort(int* arr, int begin, int end, int* temp)
//{
//	if (begin == end)  // 如果起始位置和结束位置相同，表示只有一个元素，已经有序，直接返回
//	{
//		return;
//	}
//
//	int mid = (begin + end) / 2;  // 计算中间位置
//
//	_MergeSort(arr, begin, mid, temp);  // 对左半部分进行递归排序
//	_MergeSort(arr, mid + 1, end, temp);  // 对右半部分进行递归排序
//
//	int begin1 = begin, end1 = mid;  // 第一组的起始索引和结束索引
//	int begin2 = mid + 1, end2 = end;  // 第二组的起始索引和结束索引
//	int i = begin;  // 临时数组的索引
//
//	while (begin1 <= end1 && begin2 <= end2)  // 当两组都还有元素时进行比较
//	{
//		if (arr[begin1] <= arr[begin2])  // 如果第一组的元素小于等于第二组的元素
//		{
//			temp[i++] = arr[begin1++];  // 将第一组的元素放入临时数组中，并增加相应的索引
//		}
//		else
//		{
//			temp[i++] = arr[begin2++];  // 将第二组的元素放入临时数组中，并增加相应的索引
//		}
//	}
//
//	while (begin1 <= end1)  // 如果第一组还有剩余元素，则将剩余元素依次放入临时数组中
//	{
//		temp[i++] = arr[begin1++];
//	}
//
//	while (begin2 <= end2)  // 如果第二组还有剩余元素，则将剩余元素依次放入临时数组中
//	{
//		temp[i++] = arr[begin2++];
//	}
//
//	/*
//	为什么要使用 arr+begin 和 temp+begin 作为参数呢？
//	这是因为在归并排序的过程中，我们只对数组的一个区间进行排序，而不是整个数组。
//	起始位置 begin 表示排序区间的起始位置，所以我们需要将起始位置对应的内存块复制回原数组的相应位置。
//	*/
//	memcpy(arr + begin, temp + begin, sizeof(int) * (end - begin + 1));  // 将临时数组中归并后的结果拷贝回原数组中，从起始位置开始
//
//}
//
//void MergeSort(int* arr, int length)
//{
//	int* temp = (int*)malloc(sizeof(int) * length);  // 创建临时数组用于存储归并结果
//	_MergeSort(arr, 0, length - 1, temp);  // 进行递归排序
//	free(temp);  // 释放临时数组的内存空间
//}

//2路归并，该函数是归并排序的核心代码，用于把两个有序子序列归并成一个
//low:指向第一个序列开头元素，mid：指向第一个序列末尾元素，high指向第二个序列末尾元素
//通过low,mid,high指定要归并的两个子序列的范围（这两个子序列相邻）
void Merge(int arr[], int temp[], int left, int mid, int right) {
	int i = left;    // 左子数组的起点
	int j = mid + 1; // 右子数组的起点
	int k = left;    // 临时数组的起点

	while (i <= mid && j <= right) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];
		}
	}

	// 将剩余元素复制到临时数组
	while (i <= mid) {
		temp[k++] = arr[i++];
	}

	while (j <= right) {
		temp[k++] = arr[j++];
	}

	// 将临时数组的元素复制回原数组
	for (i = left; i <= right; i++) {
		arr[i] = temp[i];
	}
}

void _MergeSort(int arr[], int* temp, int left, int right)
{
	if (left >= right)
		return;//递归出口

	int mid = (left + right) / 2; //中间分开
	_MergeSort(arr, temp, left, mid); //对左半部分归并排序
	_MergeSort(arr, temp, mid + 1, right); //对右半部分归并排序

	// 左右两个子序列分别有序之后，将它们合并成一个有序序列
	Merge(arr, temp, left, mid, right);
}

//归并排序入口（从小到大）
void MergeSort(int arr[], int length)
{
	int* temp = (int*)malloc(sizeof(int) * length);  // 创建临时数组用于存储归并结果
	_MergeSort(arr, temp, 0, length - 1); 

	free(temp);  // 释放临时数组的内存空间
}


// 归并排序非递归版
void MergeSortNonR(int* arr, int length)
{
	int* temp = (int*)malloc(sizeof(int) * length);  // 创建临时数组用于存储归并结果

	int gap = 1;  // 初始步长为1
	while (gap < length)  // 当步长小于数组长度时
	{
		int j = 0;  // 临时数组索引
		for (int i = 0; i < length; i += 2 * gap)  // 每次以两倍步长遍历数组
		{
			int begin1 = i, end1 = i + gap - 1;  // 第一组的起始索引和结束索引
			int begin2 = i + gap, end2 = i + 2 * gap - 1;  // 第二组的起始索引和结束索引

			if (end1 >= length || begin2 >= length)  // 如果某一组的索引超出数组范围，则跳出循环
			{
				break;
			}

			if (end2 >= length)  // 如果第二组的结束索引超出数组范围，则修正为数组最后一个元素的索引
			{
				end2 = length - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)  // 当两组都还有元素时进行比较
			{
				if (arr[begin1] < arr[begin2])  // 如果第一组的元素小于第二组的元素
				{
					temp[j++] = arr[begin1++];  // 将第一组的元素放入临时数组中，并增加相应的索引
				}
				else
				{
					temp[j++] = arr[begin2++];  // 将第二组的元素放入临时数组中，并增加相应的索引
				}
			}

			while (begin1 <= end1)  // 如果第一组还有剩余元素，则将剩余元素依次放入临时数组中
			{
				temp[j++] = arr[begin1++];
			}

			while (begin2 <= end2)  // 如果第二组还有剩余元素，则将剩余元素依次放入临时数组中
			{
				temp[j++] = arr[begin2++];
			}

			memcpy(arr + i, temp + i, sizeof(int) * (end2 - i + 1));  // 将临时数组中归并后的结果拷贝回原数组中
		}

		gap *= 2;  // 增加步长为原来的两倍
	}

	free(temp);  // 释放临时数组的内存空间
}



//—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
// 计数排序
// 时间复杂度：O(length+Range)
// 空间复杂度：O(Range)
// 缺陷1：依赖数据范围，适用于范围集中的数组
// 缺陷2：只能用于整形
void CountSort(int* arr, int length)
{
	// 找出数组的最小值和最大值
	int min = arr[0], max = arr[0];
	for (int i = 0; i < length; i++)
	{
		if (arr[i] < min)
			min = arr[i];

		if (arr[i] > max)
			max = arr[i];
	}

	int range = max - min + 1; // 计数数组的范围
	int* countA = (int*)malloc(sizeof(int) * range); // 计数数组
	memset(countA, 0, sizeof(int) * range); // 初始化计数数组元素都为0

	// 计数
	for (int i = 0; i < length; i++)
	{
		countA[arr[i] - min]++;
	}

	// 排序	
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
		{
			arr[k++] = j + min;
		}
	}

	// 释放计数数组
	free(countA);
}